/**
 * 给你一个整数数组cost, 其中cost[i]是从楼梯第i个台阶向上爬需要支付的费用，一旦你支付此
 * 费用，即可选择向上爬1个或两个台阶。
 * 你可以选择从下标为0或者下标为1的台阶开始爬楼梯。
 * 请你计算并返回达到楼梯顶部的最低花费
 * 示例1:
 *  输入: cost = [10, 15, 20];
 *  输出: 15
 *  解释: 你将从下标为1的台阶开始。
 *  -支付15，向上爬两个台阶，到达楼梯顶部。
 *  总花费为15
 * 示例2:
 *  输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1];
 *  输出: 6
 *  解释:
 *  -支付1，向上爬两个台阶，到达下标为2的台阶
 *  -支付1，向上爬两个台阶，到达下标为4的台阶
 *  -支付1，向上爬两个台阶，到达下标为6的台阶
 *  -支付1，向上爬一个台阶，到达下标为7的台阶
 *  -支付1，向上爬两个台阶，到达下标为9的台阶
 *  -支付1，向上爬一个台阶，到达楼梯顶部。
 *  总花费为6
*/

function minCostClimbingStairs(cost) {
    const dp = [];
    dp[0] = cost[0];
    dp[1] = cost[1];
    const n = cost.length
    // 根据要执行的问题重复执行子问题并找到边界
    for (let i = 2; i < n; i++) {
        // 定义子问题
        dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
    }
    return Math.min(dp[n - 1], dp[n - 2]);   
}

console.log(minCostClimbingStairs([10, 15, 20]));
console.log(minCostClimbingStairs([1, 100, 1, 1, 1, 100, 1, 1, 100, 1]));